//给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。 
//
// 换句话说，s1 的排列之一是 s2 的 子串 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s1 = "ab" s2 = "eidbaooo"
//输出：true
//解释：s2 包含 s1 的排列之一 ("ba").
// 
//
// 示例 2： 
//
// 
//输入：s1= "ab" s2 = "eidboaoo"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s1.length, s2.length <= 10⁴ 
// s1 和 s2 仅包含小写字母 
// 
//
// Related Topics 哈希表 双指针 字符串 滑动窗口 👍 735 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution567 {
    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> map = new HashMap<>();
        for(Character c : s1.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        while(right < s2.length()){
            char c = s2.charAt(right);
            if(need.containsKey(c)){
                map.put(c, map.getOrDefault(c, 0) + 1);
                if(map.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            //长度等于s1的时候判断字母是否对应
            while(right - left + 1 == s1.length()){ //因为这里是长度相等的时候才会进循环，删除了左边字符后长度必不相等,所以==也行
                if(valid == need.size()){
                    return true;
                }
                char key = s2.charAt(left);
                if(need.containsKey(key)){
                    if(need.get(key).equals(map.get(key))){
                        valid--;
                    }
                    map.put(key, map.get(key)-1);
                    //加了这个不行,因为这里是长度相等的时候才会进循环，删除了左边字符后长度必不相等
//                    if(map.get(key).equals(need.get(key))){
//                        valid++;
//                    }
                }
                left++;
            }
            right++;
        }
        return false;
    }

    public static void main(String[] args) {
        new Solution567().checkInclusion("adc", "dcda");
    }
}
//leetcode submit region end(Prohibit modification and deletion)
